/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algorithm.bestFirstSearch_4Q;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

/*
 迭代深化搜索, 对于一棵树
 搜索的深度不断的增加，每次从root开始搜索
 （如果已经知道目标节点很浅，则这种算法很好）

 BFS, 对于一棵树
 1）设A ＝ root
 2）搜索A节点（标记为已访问），如果找到返回
 3）将A节点的子节点入队
 4）从队头让一个节点X出队， A ＝ X， 循环到第2步
 （如果已经知道，这个棵树的分支很少，这个算法是最佳选择）
 */

/**
 * 
 * @author chenwei767
 */
public class Best_FS {

	public Best_FS() {
		closedTab = new ArrayList<Nodecb>();
		openTab = new TreeSet<Nodecb>(new Comparator<Nodecb>() {
			public int compare(Nodecb o1, Nodecb o2) {
				int left = o1.actualCost + o1.heuristic;
				int right = o2.actualCost + o2.heuristic;
				return left - right;
			}
		});
	}

	private TreeSet<Nodecb> openTab;
	private List<Nodecb> closedTab;

	public Nodecb find(Nodecb chessboard) {
		openTab.add(chessboard);
		closedTab.add(chessboard);
		return best_fs();
	}

	private Nodecb best_fs() {
		Nodecb node = new Nodecb();
		while (!openTab.isEmpty()) {
			node = openTab.first();
			openTab.remove(node);
			if (node.actualCost == 0)
				break;
			generateChildNodes(node);
		}
		return node;
	}

	private void generateChildNodes(Nodecb root) {
		// root 生成的棋盘 同时存入openTab与closedTab
		for (int i = 0; i < root.board.length; i++)
			for (int j = 0; j < root.board[i].length; j++)
				if (root.board[i][j] == true)
					createNodes(root, i, j);
	}

	private void createNodes(Nodecb root, int i, int j) {
		if (j == 0)// only can shift right
		{
			createNode(root, i, j, "right");
		} else if (j == root.board.length - 1)// only can shift left
		{
			createNode(root, i, j, "left");
		} else
		// can shift both side
		{
			createNode(root, i, j, "right");
			createNode(root, i, j, "left");
		}
	}

	public void createNode(Nodecb root, int i, int j, String arg) {
		Nodecb newNode = new Nodecb(root);
		newNode.board[i][j] = false;
		if (arg.equals("left"))
			newNode.board[i][j - 1] = true;
		else if (arg.equals("right"))
			newNode.board[i][j + 1] = true;

		if (!closedTab.contains(newNode)) {
			newNode.heuristic++;
			newNode.initActualCost();
			openTab.add(newNode);
			closedTab.add(newNode);
		}
	}
}
